SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Online algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Online algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Online_and_offline" title="Online and offline">online and offline</a>.</div>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, an <b>online algorithm</b><sup id="cite_ref-karp92_1-0" class="reference"><a href="#cite_note-karp92-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the <a href="Algorithm" title="Algorithm">algorithm</a>, without having the entire input available from the start. In contrast, an <b>offline algorithm</b> is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand.

</p><p>In <a href="Operations_research" title="Operations research">operations research</a>, the area in which online algorithms are developed is called <a href="Online_optimization" title="Online optimization">online optimization</a>.

</p><p>As an example, consider the <a href="Sorting_algorithms" class="mw-redirect" title="Sorting algorithms">sorting algorithms</a> <a href="Selection_sort" title="Selection sort">selection sort</a> and <a href="Insertion_sort" title="Insertion sort">insertion sort</a>: selection sort repeatedly selects the minimum element from the unsorted remainder and places it at the front, which requires access to the entire input; it is thus an offline algorithm. On the other hand, insertion sort considers one input element per iteration and produces a partial solution without considering future elements. Thus insertion sort is an online algorithm.

</p><p>Note that the final result of an insertion sort is optimum, i.e., a correctly sorted list. For many problems, online algorithms cannot match the performance of offline algorithms. If the ratio between the performance of an online algorithm and an optimal offline algorithm is bounded, the online algorithm is called <a href="Competitive_analysis_(online_algorithm)" title="Competitive analysis (online algorithm)">competitive</a>.<sup id="cite_ref-karp92_1-1" class="reference"><a href="#cite_note-karp92-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Not every <i>offline algorithm</i> has an efficient <i>online</i> counterpart.

</p><p>In grammar theory they are associated with <a href="Straight-line_grammar" title="Straight-line grammar">Straight-line grammars</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>Because it does not know the whole input, an online algorithm is forced to make decisions that may later turn out not to be optimal, and the study of online algorithms has focused on the quality of decision-making that is possible in this setting. <a href="Competitive_analysis_(online_algorithm)" title="Competitive analysis (online algorithm)">Competitive analysis</a> formalizes this idea by comparing the relative performance of an online and offline algorithm for the same problem instance. Specifically, the competitive ratio of an algorithm, is defined as the worst-case ratio of its cost divided by the optimal cost, over all possible inputs. The competitive ratio of an online problem is the best competitive ratio achieved by an online algorithm. Intuitively, the competitive ratio of an algorithm gives a measure on the quality of solutions produced by this algorithm, while the competitive ratio of a problem shows the importance of knowing the future for this problem.

</p>

<div class="mw-heading mw-heading3"><h3 id="Other_interpretations">Other interpretations</h3></div>

<p>For other points of view on <i>online inputs to algorithms</i>, see

</p>

<ul><li><a href="Streaming_algorithm" title="Streaming algorithm">streaming algorithm</a>: focusing on the amount of memory needed to accurately represent past inputs;</li>

<li><a href="Dynamic_algorithm" class="mw-redirect" title="Dynamic algorithm">dynamic algorithm</a>: focusing on the time complexity of maintaining solutions to problems with online inputs.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Examples">Examples</h3></div>

<p>Some <i>online algorithms</i>:

</p>

<ul><li><a href="Insertion_sort" title="Insertion sort">Insertion sort</a></li>

<li><a href="Perceptron" title="Perceptron">Perceptron</a></li>

<li><a href="Reservoir_sampling" title="Reservoir sampling">Reservoir sampling</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Odds_algorithm" title="Odds algorithm">Odds algorithm</a></li>

<li><a href="Page_replacement_algorithm" title="Page replacement algorithm">Page replacement algorithm</a></li>

<li><a href="Algorithms_for_calculating_variance" title="Algorithms for calculating variance">Algorithms for calculating variance</a></li>

<li><a href="Ukkonen's_algorithm" title="Ukkonen's algorithm">Ukkonen's algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Online_problems">Online problems</h2></div>

<p>A problem exemplifying the concepts of online algorithms is the <a href="Canadian_traveller_problem" title="Canadian traveller problem">Canadian traveller problem</a>. The goal of this problem is to minimize the cost of reaching a target in a weighted graph where some of the edges are unreliable and may have been removed from the graph. However, that an edge has been removed (<i>failed</i>) is only revealed to <i>the traveller</i> when she/he reaches one of the edge's endpoints. The worst case for this problem is simply that all of the unreliable edges fail and the problem reduces to the usual <a href="Shortest_path_problem" title="Shortest path problem">shortest path problem</a>. An alternative analysis of the problem can be made with the help of competitive analysis. For this method of analysis, the offline algorithm knows in advance which edges will fail and the goal is to minimize the ratio between the online and offline algorithms' performance. This problem is <a href="PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a>.

</p><p>There are many formal problems that offer more than one <i>online algorithm</i> as solution:

</p>

<ul><li><a href="K-server_problem" title="K-server problem"><i>k</i>-server problem</a></li>

<li><a href="Job_shop_scheduling" class="mw-redirect" title="Job shop scheduling">Job shop scheduling problem</a></li>

<li><a href="List_update_problem" title="List update problem">List update problem</a></li>

<li><a href="Bandit_problem" class="mw-redirect" title="Bandit problem">Bandit problem</a></li>

<li><a href="Secretary_problem" title="Secretary problem">Secretary problem</a></li>

<li><a href="Search_games" class="mw-redirect" title="Search games">Search games</a></li>

<li><a href="Ski_rental_problem" title="Ski rental problem">Ski rental problem</a></li>

<li><a href="Linear_search_problem" title="Linear search problem">Linear search problem</a></li>

<li>Portfolio selection problem<sup id="cite_ref-doc16_2-0" class="reference"><a href="#cite_note-doc16-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Page_replacement_algorithm" title="Page replacement algorithm">Paging problem</a></li>

<li><a href="Metrical_task_systems" class="mw-redirect" title="Metrical task systems">Metrical task systems</a></li>

<li><a href="Matching_(graph_theory)#Online_bipartite_matching" title="Matching (graph theory)">Online bipartite matching</a></li></ul>

<ul><li><a href="Adversary_(online_algorithm)" class="mw-redirect" title="Adversary (online algorithm)">Adversary model</a></li>

<li><a href="Dynamic_algorithm" class="mw-redirect" title="Dynamic algorithm">Dynamic algorithm</a></li>

<li><a href="Prophet_inequality" title="Prophet inequality">Prophet inequality</a></li>

<li><a href="Real-time_computing" title="Real-time computing">Real-time computing</a></li>

<li><a href="Streaming_algorithm" title="Streaming algorithm">Streaming algorithm</a></li>

<li><a href="Sequential_algorithm" title="Sequential algorithm">Sequential algorithm</a></li>

<li><a href="Online_machine_learning" title="Online machine learning">Online machine learning</a>/<a href="Offline_learning" title="Offline learning">Offline learning</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKarp1992" class="citation journal cs1">Karp, Richard M. (1992). <a rel="nofollow" class="external text" href="http://www.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf">"On-line algorithms versus off-line algorithms: How much is it worth to know the future?"</a> <span class="cs1-format">(PDF)</span>. <i>IFIP Congress (1)</i>. <b>12</b>: <span class="nowrap">416–</span>429<span class="reference-accessdate">. Retrieved <span class="nowrap">17 August</span> 2015</span>.</cite></span>

</li>

<li id="cite_note-doc16-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-doc16_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFDochow2016" class="citation book cs1">Dochow, Robert (2016). <a rel="nofollow" class="external text" href="https://www.springer.com/de/book/9783658135270"><i>Online Algorithms for the Portfolio Selection Problem</i></a>. Springer Gabler.</cite></span>

</li>

</ol></div></div>

<ul><li><cite id="CITEREFBorodin,_A.El-Yaniv,_R.1998" class="citation book cs1"><a href="Allan_Borodin" title="Allan Borodin">Borodin, A.</a>; El-Yaniv, R. (1998). <a rel="nofollow" class="external text" href="https://www.cs.technion.ac.il/~rani/book.html"><i>Online Computation and Competitive Analysis</i></a>. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-56392-5</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cs.ucr.edu/~marek/pubs/online.bib">Bibliography of papers on online algorithms</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1038841319">

/* start https://en.wikipedia.org/ */

.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q786431#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1492" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q786431#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1492" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Online-Algorithmus"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4583199-3">Germany</a></span></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Online algorithms"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh98004683">United States</a></span></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Algorithmes en ligne"><a rel="nofollow" class="external text" href="https://catalogue.bnf.fr/ark:/12148/cb17707903j">France</a></span></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Algorithmes en ligne"><a rel="nofollow" class="external text" href="https://data.bnf.fr/ark:/12148/cb17707903j">BnF data</a></span></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.nli.org.il/en/authorities/987007534843905171">Israel</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/concept/a5e152ba-576b-4543-bf3e-4e1a900e0564">Yale LUX</a></span></li></ul></div></td></tr></tbody></table></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures_and_algorithms145" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a> and <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data structures</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li>

<li><a href="Associative_array" title="Associative array">Associative array</a></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick tree</a></li>

<li><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graph</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment tree</a></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="String_(computer_science)" title="String (computer science)">String</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Algorithms and <a href="Algorithmic_paradigm" title="Algorithmic paradigm">algorithmic paradigms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Backtracking" title="Backtracking">Backtracking</a></li>

<li><a href="Binary_search" title="Binary search">Binary search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a></li>

<li><a href="Brute-force_search" title="Brute-force search">Brute-force search</a></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a></li>

<li><a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">Divide and conquer</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Graph_traversal" title="Graph traversal">Graph traversal</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy</a></li>

<li><a href="Hash_function" title="Hash function">Hash function</a></li>

<li><a href="Minimax" title="Minimax">Minimax</a></li>

<li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion</a></li>

<li><a href="Root-finding_algorithm" title="Root-finding algorithm">Root-finding</a></li>

<li><a href="Sorting_algorithm" title="Sorting algorithm">Sorting</a></li>

<li><a href="Streaming_algorithm" title="Streaming algorithm">Streaming</a></li>

<li><a href="Sweep_line_algorithm" title="Sweep line algorithm">Sweep line</a></li>

<li><a href="String-searching_algorithm" title="String-searching algorithm">String-searching</a></li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li>

<li><a href="List_of_algorithms" title="List of algorithms">List of algorithms</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-23" href="https://en.wikipedia.org/wiki/?title=Online_algorithm&oldid=1296980133">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>